#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int getCoins(vector<int>& coins) {
        int n = coins.size();
        vector<vector<int>> dp(n, vector<int>(n));
        for (int i = n - 1; i >= 0; i--)
        {
            for (int j = 0; j < n; j++)
            {
                int ma = 0;
                for (int k = i; k <= j; k++)
                {
                    int l = (i - 1 >= 0 ? coins[i - 1] : 1), r = (j + 1 < n ? coins[j + 1] : 1);
                    int cur = (i <= k - 1 ? dp[i][k - 1] : 0) + (k + 1 <= j ? dp[k + 1][j] : 0) + l * coins[k] * r;
                    ma = max(ma, cur);
                }
                dp[i][j] = ma;
            }
        }
        return dp[0][n - 1];
    }
};